class Solution {
    vector<vector<bool>> used;
    int row, col;
    //不能使用全局的path记录搜索路径如果在某个分支中 
    //path 被修改，其他分支也会看到这个修改，从而导致错误
    //string path;    

    //正确的做法是，边dfs，边判断走到的字符 word[index] == board[m][n] ？ 
    //如果相等，就继续遍历
    //不想等，直接返回

    bool dfs(vector<vector<char>>& board, string& word, int m, int n, int index)
    {
        if (index == word.size())
            return true;
        if (m < 0 || n < 0 || m >= row || n >= col || used[m][n] || word[index] != board[m][n])
            return false;

        used[m][n] = true;

        if (dfs(board, word, m - 1, n, index + 1) ||   //上
            dfs(board, word, m, n - 1, index + 1) ||   //左
            dfs(board, word, m + 1, n, index + 1) ||   //下
            dfs(board, word, m, n + 1, index + 1)      //右
            ){
                return true;
            }
        
        used[m][n] = false;
        return false;
    }
public:
    bool exist(vector<vector<char>>& board, string word) {
        row = board.size();
        col = board[0].size();
        for (int i = 0; i < row; i++)
            used.push_back(vector<bool>(col, false));

        //每个一点都可能是起点，所以要遍历所有点
        for (int i = 0; i < row; i++)
            for (int j = 0; j < col; j++)
                if (dfs(board, word, i, j, 0))
                    return true;
        
        return false;
    }
};